package com.mzy.linear_struct.subject;

import javax.xml.stream.events.StartElement;
import java.rmi.MarshalException;

/**
 * @Author: codermzy
 * @Date: 2024/04/15/10:33
 * @Description:
 */
public class 搜索二维矩阵74 {

    public boolean searchMatrix(int[][] matrix, int target) {

        // 获取最下面一行
        int row = matrix.length - 1; // 2
        int[] startSearch = matrix[row];
        int i = 0;
        while (row >= 0) {
            if (startSearch[i] <= target) {
                for (int j = 0; j < startSearch.length; j++) {
                    if (startSearch[j] == target) return true;
                }
                return false;
            } else if (startSearch[0] > target) {
                if (row > 0) {
                    startSearch = matrix[--row];
                } else {
                    return false;
                }
            }
        }
        return false;
    }


    public boolean searchMatrix1(int[][] matrix, int target) {

        int x = 0;
        int y = matrix.length - 1;

        while (x < matrix[0].length && y >= 0) {
            if (matrix[y][x] == target) {
                return true;
            } else if (matrix[y][x] > target) {
                y--;
            } else {
                x++;
            }

        }

        return false;
    }


    public boolean searchMatrix2(int[][] matrix, int target) {

        int row = matrix.length - 1;
        int col = matrix[0].length;

        int l = 0;
        int r = row;

        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (matrix[mid][0] <= target) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }

        row = l;
        if (matrix[row][0] == target) return true;
        if (matrix[row][0] > target) return false;


        // 第二次二分，定位列

        l = 0;
        r = matrix[row].length - 1;
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (matrix[row][mid] <= target) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return matrix[row][l] == target;
    }

    /**
     * 将二维数组看成一维数组
     */
    public boolean searchMatrix3(int[][] matrix, int target) {
        if (matrix == null) {
            return false;
        }
        if (matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int l = 0;
        int r = matrix.length * matrix[0].length - 1;

        while (l <= r) {
            int mid = (l + r) >> 1;
            int row = mid / matrix[0].length;
            int col = mid % matrix[0].length;

            if (matrix[row][col] < target) {
                l = mid + 1;
            } else if (matrix[row][col] > target) {
                r = mid - 1;
            } else {
                return true;
            }
        }

        return false;

    }

    public static void main(String[] args) {
        int[][] matrix = {
                {1}
        };
        // 1, 2, 3, 5, 6, 7, 9, 10, 11
        // 0  1  2  3  4  5  6  7   8

        // m 4
        // m 5+8>>1=6   row=6/3=2  col=6%3=0
        // m 0+0>>1=0   row=0/1=0  col=0%1=0
        // m 0+2>>1=1   row=2/2=1  col=2%2=0
        System.out.println(new 搜索二维矩阵74().searchMatrix3(matrix, 1));
    }
}
